﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TreeDemo
{
    class AVLTree : BinarySearchTree
    {
        public AVLTree(int[] input) :base(input)
        {            
        }
        private int GetHeight(BinarySearchTreeNode node)
        {
            if (node == null)
                return 0;

            else
            {
                int leftIndex = GetHeight(node.left) + 1;
                int rightIndex = GetHeight(node.right) + 1;
                return Math.Max(leftIndex, rightIndex);
            }
        }

        protected override BinarySearchTreeNode Shift(BinarySearchTreeNode node)
        {
            int leftIndex = GetHeight(node.left);
            int rightIndex = GetHeight(node.right);
            int HeightDifference = leftIndex - rightIndex;

            zNode = yNode;
            yNode = xNode;
            xNode = node;

            if (HeightDifference >= -1 && HeightDifference <= 1)
                return node;

            BinarySearchTreeNode temp = null;
            BinarySearchTreeNode temp1 = null;
            if (HeightDifference == 2)
            {
                yNode = node.left;
                if (GetHeight(node.left.left) >= GetHeight(node.left.right))
                    zNode = node.left.left;
                else
                    zNode = node.left.right;

                //if(zNode == null && yNode.left != null)
                //    zNode = yNode.left;
                if (xNode.data > yNode.data && yNode.data > zNode.data)
                {
                    xNode.left = yNode.right;
                    yNode.right = xNode;
                    temp = yNode;
                }
                else
                {
                    temp1 = zNode;
                    yNode.right = temp1.left;
                    xNode.left = temp1.right;
                    zNode.right = xNode;
                    zNode.left = yNode;
                    temp = zNode;
                }
            }
            else
            {
                yNode = node.right;
                if (GetHeight(node.right.right) >= GetHeight(node.right.left))
                    zNode = node.right.right;
                else
                    zNode = node.right.left;

                //if(zNode == null && yNode.right != null)
                //    zNode = yNode.right;
                if (xNode.data < yNode.data && yNode.data < zNode.data)
                {
                    xNode.right = yNode.left;
                    yNode.left = xNode;
                    temp = yNode;
                }
                else
                {
                    temp1 = zNode;
                    yNode.left = temp1.right;
                    xNode.right = temp1.left;
                    zNode.left = xNode;
                    zNode.right = yNode;
                    temp = zNode;
                }
            }
            if (rootNode == node)
                rootNode = temp;

            return temp;
        }
    }

    class AVLTreeNode : BinarySearchTreeNode
    {
        public AVLTreeNode(int data)
            : base(data)
        {
        }
    }
}
